// https://leetcode.cn/problems/minimum-depth-of-binary-tree/

package binarytree

// 思路：
// 1. 如果根节点为空，返回0。
// 2. 如果根节点是叶子节点（没有左子树和右子树），返回1。
// 3. 如果左子树为空，递归计算右子树的深度并加1。
// 4. 如果右子树为空，递归计算左子树的深度并加1。
// 5. 如果左右子树都存在，递归计算左子树和右子树的深度，返回较小的深度加1。
// 核心的思路中必须存在 子树的概念，当前节点的高度是基于子树的高度来计算的。
func MinDepthCopilot(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if root.Left == nil && root.Right == nil {
		return 1
	}
	if root.Left == nil {
		return MinDepthCopilot(root.Right) + 1
	}
	if root.Right == nil {
		return MinDepthCopilot(root.Left) + 1
	}
	// 此处可以保证进入递归的节点不会是 nil
	// 因为上面的判断已经处理了左子树和右子树为空的情况
	// 所以if root==nil { return 0 } 这个判断只是针对整棵树的判断，对于子树是没有意义的!!!
	leftDepth := MinDepthCopilot(root.Left)
	rightDepth := MinDepthCopilot(root.Right)
	if leftDepth < rightDepth {
		return leftDepth + 1
	}
	return rightDepth + 1
}

// The function `minDepth` calculates the minimum depth of a binary tree.
// The minimum depth is defined as the number of nodes along the shortest path from the root node down to the nearest leaf node.
// The function checks if the root is nil, in which case it returns 0.
// If the root is a leaf node (both left and right children are nil), it returns 1.
// If the left child is nil, it recursively calculates the depth of the right subtree and adds 1.
// If the right child is nil, it recursively calculates the depth of the left subtree and adds 1.
// If both children are present, it calculates the minimum depth of both subtrees and returns the smaller depth plus 1.

// 计算最大深度
// https://leetcode.cn/problems/maximum-depth-of-binary-tree/
// 思路：
// 1. 如果根节点为空，返回0。
// 2. 递归计算左子树和右子树的深度，取较大值加1。
func MaxDepthCopilot(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftDepth := MaxDepthCopilot(root.Left)
	rightDepth := MaxDepthCopilot(root.Right)
	if leftDepth > rightDepth {
		return leftDepth + 1
	}
	return rightDepth + 1
}
